\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  \texttt{1\ l\ r\ x\ y}：把区间 \([l,r]\) 中所有 \(x\) 变成 \(y\)
\item
  \texttt{2\ l\ r\ k} : 查询区间 \([l,r]\) 中的 \(k\) 小值
\item
  \(1\le n,m,a_i \le 10^5\)
\end{itemize}

\begin{lstlisting}
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
const int N = 100005, M = N - 5, S1 = 600, S2 = 280;
int sm[N / S1 + 5], tp1[N], tp2[N / S2 + 2];
int n, m, a[N], cn1[N / S1 + 5][N], cn2[N / S1 + 5][N / S2 + 5], rc[N / S1 + 5], tot[N / S1 + 5];
int cl[N / S1 + 5][S1 + 5], vl[N / S1 + 5][S1 + 5], wh[N / S1 + 5][N + S1], a1[S1 + 5], a2[N], bc1, bc2;
int b1[N], b2[N], L1[N / S1 + 5], L2[N / S2 + 5], R1[N / S1 + 5], R2[N / S2 + 5], rb[N / S1 + 5][S1 + 5];
void init()
{
	for (int i = 1; i <= M; i++) b2[i] = (i - 1) / S2 + 1;
	for (int i = 1; i <= M + 1; i++) if (b2[i] ^ b2[i - 1])
	{
		R2[bc2] = i - 1;
		if (i ^ (M + 1)) L2[++bc2] = i;
	}
	for (int i = 1; i <= n; i++) b1[i] = (i - 1) / S1 + 1;
	for (int i = 1; i <= n + 1; i++) if (b1[i] ^ b1[i - 1])
	{
		R1[bc1] = i - 1;
		if (i ^ (M + 1)) L1[++bc1] = i;
	}
	for (int i = 1; i <= bc1; i++)
	{
		int l = R1[i] - L1[i] + 1;
		for (int j = 1; j <= M; j++) cn1[i][j] = cn1[i - 1][j];
		for (int j = 1; j <= bc2; j++) cn2[i][j] = cn2[i - 1][j];
		for (int j = L1[i]; j <= R1[i]; j++) cn1[i][a[j]]++, cn2[i][b2[a[j]]]++;
		for (int j = 1; j <= l; j++) cl[i][j] = a[L1[i] + j - 1], a1[j] = a2[cl[i][j]] = !a2[cl[i][j]] ? ++tot[i] : a2[cl[i][j]];
		for (int j = 1; j <= l; j++) 
			a2[cl[i][j]] = 0, vl[i][a1[j]] = cl[i][j], wh[i][cl[i][j]] = a1[j], cl[i][j] = a1[j] + M, wh[i][cl[i][j]] = a1[j];
	}
}
void modif(int id, int l, int r, int x, int y)
{
	int nx, fg, rs = 0;
	if (cn1[id][x] == cn1[id - 1][x]) return;
	if (cn1[id][y] == cn1[id - 1][y])
	{
		if (rc[id]) fg = 1, nx = rb[id][rc[id]--];
		else fg = 0, nx = ++tot[id];
		for (int i = l; i <= r; i++) if (vl[id][wh[id][cl[id][i]]] == x) cl[id][i] = nx + M, rs++;
		if (!rs)
			return fg ? rc[id]++ : tot[id]--, void();
		else
			wh[id][y] = wh[id][nx + M] = nx, vl[id][nx] = y;
	}
	else
		for (int i = l; i <= r; i++)
			if (vl[id][wh[id][cl[id][i]]] == x)
				cl[id][i] = wh[id][y] + M, rs++;
	if (rs == cn1[id][x] - cn1[id - 1][x]) rb[id][++rc[id]] = wh[id][x], vl[id][wh[id][x]] = 0, wh[id][wh[id][x] + M] = 0, wh[id][x] = 0;
	sm[id] = rs;
}
void chang(int id, int x, int y)
{
	if (cn1[id][x] == cn1[id - 1][x]) return;
	if (cn1[id][y] == cn1[id - 1][y]) return wh[id][y] = wh[id][x], vl[id][wh[id][x]] = y, wh[id][x] = 0, void();
	int l = R1[id] - L1[id] + 1;
	for (int i = 1; i <= l; i++) if (vl[id][wh[id][cl[id][i]]] == x) cl[id][i] = wh[id][y] + M;
	rb[id][++rc[id]] = wh[id][x], vl[id][wh[id][x]] = 0, wh[id][wh[id][x] + M] = 0, wh[id][x] = 0;
}
void updat(int l, int r, int x, int y)
{
	if (x == y) return;
	else memset(sm, 0, sizeof(sm));
	int L = b1[l], R = b1[r], X = b2[x], Y = b2[y];
	if (L ^ R)
	{
		modif(L, l - L1[L] + 1, R1[L] - L1[L] + 1, x, y), modif(R, 1, r - L1[R] + 1, x, y), L++, R--;
		for (int i = L; i <= R; i++) chang(i, x, y), sm[i] = cn1[i][x] - cn1[i - 1][x];
	}
	else modif(L, l - L1[L] + 1, r - L1[L] + 1, x, y);
	for (int i = L - 1; i <= bc1; i++)
		sm[i] += sm[i - 1], cn1[i][x] -= sm[i], cn1[i][y] += sm[i], cn2[i][X] -= sm[i], cn2[i][Y] += sm[i];
}
int query(int l, int r, int x)
{
	memset(tp2, 0, sizeof(tp2));
	int L = b1[l], R = b1[r];
	if (L == R)
	{
		for (int i = l, y; i <= r; i++) y = vl[L][wh[L][cl[L][i - L1[L] + 1]]], tp1[y]++, tp2[b2[y]]++;
		for (int i = 1; i <= bc2; x -= tp2[i], i++) if (x - tp2[i] <= 0)
		{
			for (int j = L2[i];; x -= tp1[j], j++) if (x - tp1[j] <= 0)
			{
				for (int k = l; k <= r; k++) tp1[vl[L][wh[L][cl[L][k - L1[L] + 1]]]] = 0;
				return j;
			}
		}
	}
	for (int i = l, y; i <= R1[L]; i++) y = vl[L][wh[L][cl[L][i - L1[L] + 1]]], tp1[y]++, tp2[b2[y]]++;
	for (int i = L1[R], y; i <= r; i++) y = vl[R][wh[R][cl[R][i - L1[R] + 1]]], tp1[y]++, tp2[b2[y]]++;
	for (int i = 1; i <= bc2; i++) tp2[i] += cn2[R - 1][i] - cn2[L][i];
	for (int i = 1; i <= bc2; x -= tp2[i], i++) if (x - tp2[i] <= 0)
	{
		for (int j = L2[i]; j <= R2[i]; j++) tp1[j] += cn1[R - 1][j] - cn1[L][j];
		for (int j = L2[i];; x -= tp1[j], j++) if (x - tp1[j] <= 0)
		{
			for (int k = L2[i]; k <= R2[i]; k++) tp1[k] = 0;
			for (int k = l; k <= R1[L]; k++) tp1[vl[L][wh[L][cl[L][k - L1[L] + 1]]]] = 0;
			for (int k = L1[R]; k <= r; k++) tp1[vl[R][wh[R][cl[R][k - L1[R] + 1]]]] = 0;
			return j;
		}
	}
	return -1; // 出错 
}
signed main()
{
	cin >> n >> m;
	rep(i, 1, n) cin >> a[i];
	init();
	while (m--)
	{
		int op, l, r, x, y;
		cin >> op >> l >> r >> x;
		if (op == 1)
		{
			cin >> y;
			updat(l, r, x, y);
		}
		else
		{
			cout << query(l, r, x) << '\n';
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
